package com.day2_链表;

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：剑指 Offer 35. 复杂链表的复制
 * 题目内容：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *
 * 难点：复制任意指针的指向
 * 时长：
 * 日期：20220820
 */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
class Solution2 {
    //这是错误写法，自己写没写出来
//    public Node copyRandomList(Node head) {
//        if(head==null) return null;
//        Node newHead=null;
//        Node last=null;
//        //第一步复制单链表
//        Node p=head;
//        while (p!=null){
//            Node newNode=new Node(p.val);
//            if(newHead==null){
//                newHead=newNode;
//                last=newNode;
//            }
//            else{
//                last.next=newNode;
//                last=newNode;
//            }
//            p=p.next;
//        }
//        //第二步复制任意指针
//        Node temp1=head;
//        Node temp2=newHead;
//        while(temp1!=null){
//            temp2.random=temp1.random;
//            temp1=temp1.next;
//            temp2=temp2.next;
//        }
//        return newHead;
//    }

    /*
    法一：哈希表
    思路：利用哈希表HashMap()的特性，构建原链表结点和新链表结点的键值对映射关系，然后再遍历原链表，同时构建新链表的next和random指针的指向
    时间复杂复分析：遍历原链表为O(n),所以为O(n)
    空间复杂度，因为用了哈希表，需要用n个数组空间去存储，所有空间复杂度为O(n)
     */
    public Node copyRandomList(Node head){
        if(head==null) return null;
        Node cur=head;
        //建立一个哈希表,构建原链表结点和新链表结点的键值对映射关系
        Map<Node,Node> map = new HashMap<>();
        while(cur!=null){
            Node node=new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }
        //然后再遍历原链表，同时构建新链表的next和random指针的指向
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);//这个就是新链表的头结点
    }

    /**
     *法二：拼接+拆分
     * 思路：先将新链表的每个后面连到原链表的每个结点后面，A->A'->B->B'->C->C'->null
     * 然后原链表结点的next结点的next结点就是新链表的next结点
     * 原链表结点的random结点的next结点就是新链表的random结点
     */
    public Node copyRandomList2(Node head){
        if(head==null) return null;
        Node cur=head;
        //1.拼接
        //先将新链表的每个后面连到原链表的每个结点后面，A->A'->B->B'->C->C'->null
        while(cur!=null){
            Node node=new Node(cur.val);
            node.next=cur.next;
            cur.next=node;
            cur=node.next;

        }
        cur=head;
        //原链表结点的random结点的next结点就是新链表的random结点,A->A'->B->B'->C->C'->null
        while(cur!=null){
            //原链表中结点的random为null的需要单独处理，因为原链表中结点的random为null，
            // 在新链表的对应的结点也为空，这个时候因为null没有成双，不做任何操作就可以让新链表对应的结点就为空了
            if(cur.random!=null)
                cur.next.random=cur.random.next;
            cur=cur.next.next;
        }

        //2.拆分
        cur=head;
        Node temp=cur.next;
        Node res=head.next;
        while(cur.next.next!=null){
            cur.next=cur.next.next;
            temp.next=temp.next.next;
            cur=cur.next;
            temp=temp.next;
        }
        //单独处理原链表的尾结点
        cur.next=null;//拆分后A->B->C->C`->null,需要去掉C`
        //返回新链表的头结点
        return res;//不能直接返回head.next,因为上面进行了拆分操作，直接返回head.next其实是返回了原结点的第二个结点。
    }


}
public class 剑指Offer35_复杂链表的复制 {
    public static void main(String[] args) {

    }
}
